// https://www.lintcode.com/problem/subarray-sum/my-submissions

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: A list of integers includes the index of the first number and the index of the last number
     */
    vector<int> subarraySum(vector<int> &nums) {
        vector<int> res;
        if (nums.empty()) {
            return res;
        }
        int sum = 0;
        map<int, int> rec;
        rec[0] = -1;
        for (int i = 0; i < nums.size(); ++i) {
            sum += nums[i];
            if (rec.find(sum) != rec.end()) {
                res.push_back(rec[sum] + 1);
                res.push_back(i);
            }
            rec[sum] = i;
        }
        return res;
    }
};